#include <bits/stdc++.h>
using namespace std;

/*
2435. 矩阵中和能被 K 整除的路径
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。

 

示例 1：



输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。
示例 2：


输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。
示例 3：


输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 5 * 104
1 <= m * n <= 5 * 104
0 <= grid[i][j] <= 100
1 <= k <= 50
*/

// 法一
class Solution {
public:
    const int MOD = 1e9 + 7;
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        // 前缀数组 prev[j][r] 上一行第j列，余数为r的路径数
        vector<vector<int>> prev(n, vector<int>(k, 0));

        // init start
        int start_mod = (grid[0][0] % k + k) % k;
        prev[0][start_mod] = 1;

        // fill
        for (int j = 1; j < n; ++j) {
            for (int r = 0; r < k; ++r) {
                int curr_val = grid[0][j];
                int prev_r = (r - (curr_val % k) + k) % k; // 前序余数
                prev[j][r] = prev[j-1][prev_r];
            }
        }

        // fill last
        for (int i = 1; i < m; i++) {
            vector<vector<int>> curr(n, vector<int>(k, 0));
            // 上到下
            for (int r = 0; r < k; ++r) {
                int curr_val = grid[i][0];
                int prev_r = (r - (curr_val % k) + k) % k;
                curr[0][r] = prev[0][prev_r];
            }
            // cur row other col
            for (int j = 1; j < n; ++j) {
                int curr_val = grid[i][j];
                int val_mod = (curr_val % k + k) % k; // 当前元素的模

                for (int r = 0; r < k; ++r) {
                    int prev_r = (r - val_mod + k) % k; // 前序余数
                    // 从上方来：prev[j][prev_r]；从左方来：curr[j-1][prev_r]
                    curr[j][r] = (prev[j][prev_r] + curr[j-1][prev_r]) % MOD;
                }
            }
            prev = move(curr);
        }
        return prev[n - 1][0];
    }
};

// 法二
const auto _ = std::cin.tie(nullptr)->sync_with_stdio(false);	// 关闭同步 提高IO

// local test
#define LC_HACK
#ifndef LC_HACK
const auto __ = []() {
	struct __
	{
		static void _() {
			std::ofstream("1.txt") << 0 << std::endl;
		} 
	};
	std::atexit(&__::_);
	return 0;
} ();
#endif	// LC_HACK

class Solution {
public:
	const int mod = 1e9 + 7;
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        // transform dp
		const int m = grid.size();    // 矩阵行数
        const int n = grid[0].size(); // 矩阵列数

		// DP表定义: dp[j][r] 表示到达当前行的第j列（对应grid[i][j-1]）时，
        // 路径和对k取模余数为r的路径数量。
        // 维度为 (n+1) x k，是为了方便处理j=1时，左侧有j-1=0的情况。
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(k, 0));

		// init start
		dp[0][0] = 1;
		for (int i = 0; i < m; i++) {
			for (int j = 1; j <= n; j++) {
				// merge path
				//    dp[j] 目前存储的是从上一行(i-1)到达当前列(j)的路径数。
                //    dp[j-1] 存储的是从当前行(i)的上一列(j-1)到达当前列(j)的路径数。
                //    使用transform将这两部分路径数相加，实现状态转移的第一步：
                //    dp[j][r] = (来自上方的路径数 + 来自左方的路径数) % mod
				std::transform(dp[j-1].begin(), dp[j-1].end(), dp[j].begin(), dp[j].begin(), [this](int left, int up) {
					return (left + up) % mod;
				});

				// cur member
				//    现在，dp[j][r] 表示到达 (i, j-1) 且路径和模k余r的路径数。
                //    当我们加上 grid[i][j-1] 后，新的余数变为 (r + grid[i][j-1]) % k。
                //    我们使用std::rotate来高效地更新这个余数状态。
				int val = grid[i][j - 1];
				int step = (val % k + k) % k;
				if (step != 0)	std::rotate(dp[j].begin(), dp[j].end() - step, dp[j].end());
			}
			dp[0][0] = 0;
		}
		return dp[n][0];
    }
};